home *** CD-ROM | disk | FTP | other *** search
/ Developer CD Series 2000 November: Tool Chest / Dev.CD Nov 00 TC Disk 2.toast / pc / sample code / overview / dtscpluslibrary / headers / collectionclasses.h < prev    next >
Encoding:
Text File  |  2000-09-28  |  6.5 KB  |  220 lines
  1. /*
  2.     File:        CollectionClasses.h
  3.  
  4.     Contains:    The following collection classes are implemented: TLinkedList, TStack, (TQueue, TDeQueue),
  5.                   THashTable.
  6.                   CollectionClasses.h contains the collection class definitions. 
  7.  
  8.     Written by: Kent Sandvik    
  9.  
  10.     Copyright:    Copyright © 1992-1999 by Apple Computer, Inc., All Rights Reserved.
  11.  
  12.                 You may incorporate this Apple sample source code into your program(s) without
  13.                 restriction. This Apple sample source code has been provided "AS IS" and the
  14.                 responsibility for its operation is yours. You are not permitted to redistribute
  15.                 this Apple sample source code as "Apple sample source code" after having made
  16.                 changes. If you're going to re-distribute the source, we require that you make
  17.                 it clear in the source that the code was descended from Apple sample source
  18.                 code, but that you've made changes.
  19.  
  20.     Change History (most recent first):
  21.                 8/18/1999    Karl Groethe    Updated for Metrowerks Codewarror Pro 2.1
  22.                 
  23.  
  24. */
  25. // Declare label for this header file
  26. #ifndef _COLLECTION__
  27. #define _COLLECTION__
  28.  
  29. #ifndef _DTSCPLUSLIBRARY_
  30. #include "DTSCPlusLibrary.h"
  31. #endif
  32.  
  33. //    GLOBAL CONSTRUCTS
  34. typedef unsigned long TItemtype;
  35. //typedef void* TItemtype;
  36.  
  37. // Note that we need to define this for the collecion items --
  38. // when we have tempates this will be moot!
  39. // Note that void* is the most practical one concerning storing
  40. // data structure pointers in lists, queues and stacks (typedef void * TItemtype)
  41.  
  42. const kCollectionSize = 200;                    // tune this concerning performance
  43.  
  44.  
  45. // _________________________________________________________________________________________________________ //
  46. //    TLinkedList Class Interface.
  47.  
  48. class TLinkedList
  49. {
  50. public:
  51.     //    CONSTRUCTORS AND DESTRUCTORS
  52.     TLinkedList(short max = kCollectionSize);
  53.     virtual~ TLinkedList();
  54.  
  55.     // MAIN INTERFACES
  56.     virtual Boolean Append(const TItemtype item);// add an entry to the linked list
  57.     virtual Boolean Remove(const TItemtype item);// remove defined item from the linked list
  58.  
  59.     virtual Boolean IsEmpty();                    // check if the collection has zero entries
  60.     virtual Boolean Find(const TItemtype item);    // find out if a special item type is in the list
  61.  
  62.     virtual Size GetSize() const;                // get amount of entries in collection
  63.  
  64.     // ITERATORS
  65.     virtual TItemtype First();                    // return first entry
  66.     virtual TItemtype Next();                    // return next entry
  67.     virtual TItemtype Last();                    // return last entry
  68.     virtual void Reset();                        // move iterator to first entry        
  69.  
  70.     //    FIELDS
  71. protected:
  72.     short fMaxCollectionSize;                    // max entries in the collection
  73.     short fCollectionSize;                        // current amount of entries in the collection
  74.     struct fNODE                                // our pointer list structure
  75.     {
  76.         TItemtype fKey;
  77.         struct fNODE *fNext;
  78.         struct fNODE *fPrevious;                // for future use
  79.     };
  80.  
  81.  
  82.     struct fNODE *fHead, * fTail, * fLastEntry, * fCurrentNode;
  83.     // linked list pointers: forward, backward, last entry, current
  84. };
  85.  
  86.  
  87. // _________________________________________________________________________________________________________ //
  88. //    TStack Class Interface.
  89.  
  90. class TStack : public TLinkedList
  91. {
  92. public:
  93.     // CONSTRUCTORS AND DESTRUCTORS
  94.     TStack(short max = kCollectionSize);
  95.     virtual~ TStack();
  96.  
  97.     // MAIN INTERFACES
  98.     virtual Boolean Push(const TItemtype item);    // push on the 'stack'
  99.     virtual Boolean Append(const TItemtype item);// will just call push anyway
  100.     virtual TItemtype Pop();                    // pop from the 'stack'
  101.     virtual Boolean Remove(const TItemtype item);// not supported, will return false
  102. };
  103.  
  104.  
  105. class TQueue : public TLinkedList
  106. {
  107. public:
  108.     // CONSTRUCTORS AND DESTRUCTORS
  109.     TQueue(short max = kCollectionSize);
  110.     ~TQueue();
  111.  
  112.     // MAIN INTERFACE
  113.     virtual Boolean Put(const TItemtype item);    // put at the beginning of the queue
  114.     virtual Boolean Append(const TItemtype item);// will just call put anyway
  115.     virtual TItemtype Get();                    // get from the end of the queue
  116.     virtual TItemtype Last();                    // get the one at the end
  117.     virtual Boolean Remove(const TItemtype item);// not supported, will return false
  118. };
  119.  
  120.  
  121. class TDeque : public TQueue
  122. {
  123. public:
  124.     // CONSTRUCTORS AND DESTRUCTORS
  125.     TDeque(short max = kCollectionSize);
  126.     virtual~ TDeque();
  127.  
  128.     // MAIN INTERFACE
  129.     virtual Boolean Push(const TItemtype item);    // will call Put anyway
  130.     virtual Boolean PutAtEnd(const TItemtype item);// add entry to the end of the dequeue
  131.  
  132.     virtual TItemtype Pop();                    // remove from beginning of deque
  133. };
  134.  
  135.  
  136.  
  137. // _________________________________________________________________________________________________________ //
  138. //    THashEntry Class Interface.
  139.  
  140. // globals, constants, enums and typedefs
  141. const unsigned long kResourceIDMask = 0xFFFFF;
  142. const NBUCKETS = 256;                            // amount of buckets in our hash entry array    
  143.  
  144.  
  145. typedef unsigned long THashKey;                    // define our hash key type
  146. typedef void(* MapFun)(void*);                    // our MapCar function definition
  147.  
  148.  
  149. // Our Hash Bucket entry data structure
  150. class THashEntry                                // embedded bucket for hash ptrs and values
  151. {
  152. public:
  153.     THashKey fKey;                                // hash key
  154.     TItemtype fValue;                            // value in bucket
  155.     THashEntry* fNext, * fPrevious;                // pointers to other buckets
  156.  
  157.     THashEntry(THashKey key)                    // constructor for this mini class
  158.     {
  159.         fKey = key;
  160.         fNext = NULL;
  161.         fPrevious = NULL;
  162.     }
  163.  
  164.  
  165.     ~THashEntry()
  166.     {
  167.         if (fNext)
  168.             fNext->fPrevious = fPrevious;
  169.         if (fPrevious)
  170.             fPrevious->fNext = fNext;
  171.     }
  172. };
  173.  
  174.  
  175. typedef THashEntry* THashEntryPtr;                // we are using a ptr quite a lot in the THashTable implementation
  176.  
  177.  
  178. // The THashTable class definition
  179. class THashTable
  180. {
  181. public:
  182.     // CONSTRUCTORS AND DESTRUCTORS
  183.     THashTable();
  184.     virtual~ THashTable();
  185.  
  186.     // MAIN INTERFACE
  187.     virtual Boolean Add(THashKey key,
  188.                         TItemtype value);        // add to hash table
  189.     virtual Boolean Remove(THashKey key);        // remove from hash table
  190.     virtual TItemtype Find(THashKey key);        // find entry in hash table
  191.     virtual void MapCar(MapFun function);        // iterate with a function over hash table entries
  192.  
  193.  
  194.     // PRIVATE INTERNAL FUNCTIONS
  195. protected:
  196.     THashEntryPtr AddElement(THashKey key);        // add an element to the hash table
  197.     virtual THashKey Hash(THashKey key);        // create the hash value
  198.     virtual THashEntryPtr FindInBucket(THashEntryPtr p,
  199.                                        // find inside the bucket the element
  200.                                        THashKey key);
  201.  
  202.     // FIELDS
  203. protected:
  204.     THashEntryPtr fBucket[NBUCKETS];            // our internal class bucket with entries
  205. };
  206.  
  207.  
  208. #endif
  209.  
  210. // _________________________________________________________________________________________________________ //
  211.  
  212.  
  213. /*    Change History (most recent last):
  214.   No        Init.    Date        Comment
  215.   1            khs        11/7/92        New file
  216.   2            khs        11/28/92    Added TLinkedList
  217.   3            khs        11/29/92    Added TQueue and TDeque
  218.   4            khs        1/14/93        Cleanup
  219. */
  220.